package com.fw.leetcode.stack;

import com.fw.leetcode.LeetCode;

import java.util.ArrayDeque;

/**
 * 20. Valid Parentheses
 *
 * Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
 * An input string is valid if:
 *  Open brackets must be closed by the same type of brackets.
 *  Open brackets must be closed in the correct order.
 *  Every close bracket has a corresponding open bracket of the same type.
 *
 * Example 1:
 *  Input: s = "()"
 *  Output: true
 *
 * Example 2:
 *  Input: s = "()[]{}"
 *  Output: true
 *
 * Example 3:
 *  Input: s = "(]"
 *  Output: false
 *
 * Constraints:
 *  1 <= s.length <= 10^4
 *  s consists of parentheses only '()[]{}'.
 */
public class Num_0020 implements LeetCode {
    private interface Solution {
        boolean isValid(String s);

        default void assertEquals(String s, boolean expected) {
            if (isValid(s) != expected) {
                isValid(s);
            }
        }
    }

    private static class MyOptimizeSolution implements Solution {

        @Override
        public boolean isValid(String s) {
            /*
             * 有效括号
             * ()[]{}
             * ()[{}
             * (
             * ([{]})
             */
            if ((s.length() & 0x1) > 0) return false; // 奇数时，肯定不成对
            int half = s.length() >> 1;
            char[] chars = new char[half]; // 栈，成对出现只需一半
            int size = 0;
            for (char c : s.toCharArray()) {
                if (c == '(') {
                    if (size >= half) return false;
                    chars[size++] = ')';
                } else if (c == '{') {
                    if (size >= half) return false;
                    chars[size++] = '}';
                } else if (c == '[') {
                    if (size >= half) return false;
                    chars[size++] = ']';
                } else if (size > 0) {
                    if (c != chars[--size]) {
                        return false;
                    }
                } else {
                    return false;
                }
            }
            return size == 0;
        }
    }

    private static class MySolution implements Solution {

        @Override
        public boolean isValid(String s) {
            /*
             * 有效括号
             * ()[]{}
             * ()[{}
             * (
             * ([{]})
             */
            ArrayDeque<Character> stack = new ArrayDeque<>();
            int i = 0;
            while (i < s.length()) {
                char c = s.charAt(i);
                switch (c) {
                    case '(':
                    case '{':
                    case '[':
                        stack.push(c);
                        break;
                    case ')':
                        if (stack.isEmpty() || '(' != stack.pop()) return false;
                        break;
                    case '}':
                        if (stack.isEmpty() || '{' != stack.pop()) return false;
                        break;
                    case ']':
                        if (stack.isEmpty() || '[' != stack.pop()) return false;
                        break;
                    default:
                        return false;
                }
                i++;
            }
            return stack.isEmpty();
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyOptimizeSolution();
        solution.assertEquals("()", true);
        solution.assertEquals("()[]{}", true);
        solution.assertEquals("(]", false);
        solution.assertEquals("(", false);
        solution.assertEquals("]", false);
    }
}
